Depression is prevalent and depressed individuals are at increased risk for numerous physical health problems. More physical activity decreases risk of physical health problems, and there is growing evidence that physical activity reduces depression symptoms. However, depressed individuals have low rates of physical activity and poor adherence to exercise interventions relative to non-depressed groups. This is likely due, at least in part, to specific core features of depression such as anhedonia (lack of enjoyment), amotivation, and fatigue, as well poorer problem-solving abilities which may impede the ability to cope with cognitive/ affective and environmental barriers to exercise. Previous research on physical activity in depressed populations has focused primarily on whether physical activity is an efficacious treatment for depression. However, virtually no research has addressed key questions about optimal strategies for increasing and maintaining physical activity in depressed individuals. We propose a randomized clinical trial in which 240 depressed individuals are assigned to one of three arms, with each successive arm having an added component that may serve to increase and maintain physical activity: 1) brief advice (BA) to exercise (control condition); 2) BA + supervised & home-based exercise (SHE)+ health education(HE) contact control; and 3) BA+SHE+ cognitive-behavioral sessions focused on increasing and maintaining exercise (CBEX). There are two phases for participants: intervention phase (3 months), which consists of intensive contact, and the follow-up phase (6 months). BA will consist of one, 45-minute session about public health recommendations and strategies for getting started. SHE will be a 12-week intervention consisting of 1x/week supervised exercise plus exercise prescriptions for home-based exercise with the goal of gradually achieving the public health recommendation of 150 minutes/ week of moderate-to-vigorous physical activity (MVPA). CBEX and HE sessions will be individual, 30-minute, weekly sessions during the intervention phase. CBEX will address barriers to physical activity that are particularly pronounced in depression, as well as problem-solving skills for coping with barriers. During the follow-up phase, groups who received SHE during the intervention phase will receive brief, monthly phone check-ins from an exercise specialist. Our primary aims are to: compare the efficacy of the 3 arms for increasing MVPA during the 12-week intervention phase and during the 6 month follow-up phase. Secondary aims include: to assess the impact of the interventions on depression and physical health outcomes; to determine whether amount of MVPA mediates the association between group assignment and change in depressive symptoms; to examine behavior change theory-based mediators of the association between group assignment and MVPA; and to examine whether social and environmental barriers to exercise predict exercise maintenance. Given high rates of depression and associated morbidity and mortality, it is critical to evaluate whether how best to combine exercise interventions to increase MVPA in both the shorter- and longer- term.